package datastructure.list;

import lombok.AllArgsConstructor;
import lombok.NoArgsConstructor;

/**
 * DESCRIPTION: 双向链表
 * Author: ammar
 * Date:   2021/12/9
 * Time:   下午12:47
 */
public class DuLinkedList<E> extends AbstractList<E> {

    private Node<E> first;
    private Node<E> last;

    @Override
    public void clear() {
        size = 0;
        first = null;
        last = null;
    }

    @Override
    public void add(int index, E e) {
        // 获取 index 前一个位置
        rangeCheckAdd(index);
        if (index == 0) {
            Node<E> newNode = new Node<>(e, null, first);
            if (first != null) {
                first.prev = newNode;
            } else {
                last = newNode;
            }
            first = newNode;
        } else if (index == size) {
            last.next = new Node<>(e, last, null);
            last = last.next;
        } else {
            Node<E> node = nodeOfIndex(index);
            Node<E> newNode = new Node<>(e, node.prev, node);
            node.prev.next = newNode;
            node.prev = newNode;
        }
        size++;
    }

    @Override
    public E get(int index) {
        return nodeOfIndex(index).element;
    }

    @Override
    public void set(int index, E e) {
        Node<E> node = nodeOfIndex(index);
        node.element = e;
    }

    @Override
    public E remove(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (node.next == null) {
            first = last = null;
        } else {
            node = nodeOfIndex(index);
            if (node.prev == null) {
                node.next.prev = null;
                first = node.next;
            } else if (node.next == null) {
                node.prev.next = null;
                last = node.prev;
            } else {
                node.next.prev = node.prev;
                node.prev.next = node.next;
            }
        }
        size--;
        return node.element;
    }

    @Override
    public int indexOf(E e) {
        Node<E> node = first;
        if (e == null) {
            for (int i = 0; i < size; i++) {
                if (node.element == null) return i;

                node = node.next;
            }
        } else {
            for (int i = 0; i < size; i++) {
                if (e.equals(node.element)) return i;
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 获取 index 位置的 node
     *
     * @param index
     * @return
     */
    private Node<E> nodeOfIndex(int index) {
        rangeCheck(index);
        Node<E> node = first;
        if (index < size << 1) {
            for (int i = 0; i < index; i++) {
                node = node.next;
            }
        } else {
            for (int i = size - 1; i > index; i--) {
                node = node.prev;
            }
        }
        return node;
    }

    @Override
    public String toString() {
        if (first == null) return "链表是空链表";
        Node node = first;
        StringBuffer sb = new StringBuffer();
        sb.append(node.element);
        for (int i = 0; i < size - 1; i++) {
            sb.append("-").append(node.next.element);
            node = node.next;
        }
        return sb.toString();
    }

    @AllArgsConstructor
    @NoArgsConstructor
    private static class Node<E> {
        E element;
        Node<E> prev;
        Node<E> next;

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();

            if (prev != null) {
                sb.append(prev.element);
            } else {
                sb.append("null");
            }

            sb.append("_").append(element).append("_");

            if (next != null) {
                sb.append(next.element);
            } else {
                sb.append("null");
            }

            return sb.toString();
        }
    }
}
